package com.example.algorithm.service.impl;

import com.example.algorithm.service.BaseService;

/**
 * @author Administrator
 * @date 2024/10/23 10:19
 * @description
 */
public class BaseServiceImpl implements BaseService {

    /**
     * 快速排序
     * @param arr
     * @param low
     * @param high
     */
    @Override
    public void quickSort(int[] arr, int low, int high) {
       if(low<high){
           int pi = partition(arr,low,high);
           quickSort(arr,low,pi-1);
           quickSort(arr,pi+1,high);
       }


    }

    /**
     * 分区方法,获取分区索引
     * @param arr
     * @param low
     * @param high
     * @return
     */
    public  int partition(int[] arr, int low, int high){
        //选择最后一个元素作为基准
      int pivot = arr[high];
      //i是小于基准的元素的索引
      int i = low-1;
      for(int j=low;j<high;j++){
          // 如果当前元素小于或等于基准
          if(arr[j]<=pivot){
           i++;
           //交换arr[i]和arr[j]
           int temp = arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
          }
      }
      //交换arr[i+1]和基准元素
      int temp =arr[i+1];
      arr[i+1]=arr[high];
      arr[high]=temp;
      return i+1;
    }



}

